/*
 * @(#)LocalSearch.java
 */
package jp.ac.kobe_u.cs.cream;

import jp.ac.kobe_u.cs.cream.*;
import java.util.*;

/**
 * A super class of local search solvers, and also
 * an implementation of a random walk solver.
 * Local search is an iterative procedure.
 * It first finds an initial soluttion, and iteratively
 * make a small change
 * @see	Solver
 * @since 1.0
 * @version 1.0, 01/31/03
 * @author Naoyuki Tamura (tamura@kobe-u.ac.jp)
 */
public class LocalSearch extends Solver {
    public long iterationTimeout = 5000;
    protected int iteration = 0;
    protected DefaultSolver solver = null;
    private boolean newCandidate = false;
    private Solution candidate = null;
    private double exchangeRate = 0.5;

    /**
     * Constructs a random-walk solver for the given network.
     * This constructor is equivalent to <tt>LocalSearch(network, DEFAULT, null)</tt>.
     * @param network the constraint network
     */
    public LocalSearch(Network network) {
	this(network, DEFAULT, null);
    }

    /**
     * Constructs a random-walk solver for the given network and option.
     * This constructor is equivalent to <tt>LocalSearch(network, option, null)</tt>.
     * @param network the constraint network
     * @param option the option for search strategy
     */
    public LocalSearch(Network network, int option) {
	this(network, option, null);
    }

    /**
     * Constructs a random-walk solver for the given network and name.
     * This constructor is equivalent to <tt>LocalSearch(network, DEFAULT, name)</tt>.
     * @param network the constraint network
     * @param name the name of the solver
     */
    public LocalSearch(Network network, String name) {
	this(network, DEFAULT, name);
    }

    /**
     * Constructs a random-walk solver for the given network, option, and name.
     * @param network the constraint network
     * @param option the option for search strategy, or DEFAULT for default search strategy
     * @param name the name of the solver, or <tt>null</tt> for a default name
     */
    public LocalSearch(Network network, int option, String name) {
	super(network, option, name);
    }

    /**
     * Sets a candidate solution for a next iteration.
     * @param candidate the candidate
     */
    public synchronized void setCandidate(Solution candidate) {
	if (candidate != null) {
	    this.candidate = candidate;
	    newCandidate = true;
	}
    }

    protected synchronized Solution candidate() {
	if (newCandidate) {
	    newCandidate = false;
	    return candidate;
	} else if (solution != null) {
	    return solution;
	}
	return bestSolution;
    }

    public void setExchangeRate(double rate) {
	exchangeRate = rate;
    }

    public double getExchangeRate() {
	return exchangeRate;
    }

    public synchronized void stop() {
	if (solver != null)
	    solver.stop();
	super.stop();
    }

    protected void startSearch() {
	solver = new DefaultSolver(network, option);
	solution = solver.findFirst();
    }

    protected void nextSearch() {
	solution = candidate();
	Code code = solution.getCode();
	List operations = code.operations();
	while (operations.size() > 0) {
	    int i = (int)(operations.size() * Math.random());
	    Operation op = (Operation)operations.remove(i);
	    code.setTo(network);
	    op.applyTo(network);
	    Solution sol = solver.findBest(iterationTimeout);
	    if (sol == null)
		continue;
	    solution = sol;
	    return;
	}
	solution = null;
    }

    protected void endSearch() {
	solver = null;
    }

    public void run() {
	iteration = 0;
	clearBest();
	startSearch();
	while (! isAborted() && solution != null) {
	    iteration++;
	    success();
	    if (isAborted())
		break;
	    nextSearch();
	    if (isAborted())
		break;
	    if (solution == null) {
		solution = bestSolution;
	    }
	}
	fail();
	endSearch();
    }

}
